import math

def getSlope(start, target):
    x1,y1 = start
    x2,y2 = target
    
    rise = math.fabs(y1 - y2)
    run = math.fabs(x1 - x2)
    
    if rise == 0:
        run = 1
    elif run == 0:
        rise = 1
    else:
        for i in reversed(range(1,int(rise+1))):
            if rise % i == 0 and run % i == 0:
                rise = rise//i
                run = run//i
                break
        
    if x1 > x2:
        run = run * -1
    if y1 > y2:
        rise = rise * -1

    return int(rise), int(run)

#Brute force, recursive path finding algorithm
def pathSearch(start, goal, steps, grid):
    col,row = start
    
    if col < 0 or row < 0 or col >= len(grid[0]) or row >= len(grid):
        return False
    
    if steps == -1 or grid[row][col] == 1:
        return False
    
    if start == goal:
        return True
    
    #try to trim bad paths early
    distance = math.fabs(start[0]-goal[0]) + math.fabs(start[1]-goal[1])
    if distance > steps:
        return False
    
    found = pathSearch((col, row-1), goal, steps-1, grid)
    if not found:
        found = pathSearch((col+1, row), goal, steps-1, grid)
    if not found:
        found = pathSearch((col, row+1), goal, steps-1, grid)
    if not found:
        found = pathSearch((col-1, row), goal, steps-1, grid)
        
    return found

def manhattan(start, end):
    return math.fabs(start[0] - end[0]) + math.fabs(start[1] - end[1])

def lineOfSight(src, dest, gameState):
                        rise, run = getSlope(src, dest)
                        lineOfSight = True
                        
                        blockedVertices = gameState["blockedVertices"]
                        obstacles = gameState["obstacles"]
                        #check for clear line of sight (no obstacles)
                        while src != dest:
                            x,y = src
                            if src in blockedVertices:
                                lineOfSight = False
                                break
                            if x%50 != 0 and y%50 != 0:
                                for o in obstacles:
                                    if o.collidepoint(src):
                                        lineOfSight = False
                                        break
                            
                            x = x + run
                            y = y + rise
                            src = (x,y)
                        
                        return lineOfSight
    